package leetcode.weekly.week327;

import java.util.PriorityQueue;

//Solution4Test
public class Solution4 {

	public int findCrossingTime(int n, int k, int[][] time) {
		// 谁index，lr+rl
		PriorityQueue<int[]> left = new PriorityQueue<>((a, b) -> a[1] == b[1] ? b[0] - a[0] : b[1] - a[1]);
		// 谁index，左岸桥边回到左岸桥边时间
		PriorityQueue<int[]> ll = new PriorityQueue<>((a, b) -> a[1] - b[1]);
		PriorityQueue<int[]> right = new PriorityQueue<>((a, b) -> a[1] == b[1] ? b[0] - a[0] : b[1] - a[1]);
		// 谁index，左岸桥边回到左岸桥边时间
		PriorityQueue<int[]> rr = new PriorityQueue<>((a, b) -> a[1] - b[1]);
		int[] sum = new int[k];
		int[] l = new int[k];// left to right
		int[] r = new int[k];// right to left
		int[] o = new int[k];// pickold
		int[] w = new int[k];// picknew
		for (int i = 0; i < time.length; i++) {
			int[] t = time[i];
			l[i] = t[0];
			r[i] = t[2];
			o[i] = t[1];
			w[i] = t[3];
			sum[i] = l[i] + r[i];
			left.add(new int[] { i, sum[i] });
		}
		int t = 0;// 桥空余的时间点
		while (n > 0) {
			while (!ll.isEmpty() && ll.peek()[1] <= t) {
				int[] cur = ll.poll();
				left.add(new int[] { cur[0], sum[cur[0]] });
			}
			while (!rr.isEmpty() && rr.peek()[1] <= t) {
				int[] cur = rr.poll();
				right.add(new int[] { cur[0], sum[cur[0]] });
			}
			if (!right.isEmpty()) {
				int[] cur = right.poll();
				int idx = cur[0], s = cur[1];
				t += r[idx];
				int next = t + w[idx];
				ll.add(new int[] { idx, next });
				continue;
			}
			if (!left.isEmpty()) {
				int[] cur = left.poll();
				int idx = cur[0], s = cur[1];
				t += l[idx];
				int next = t + o[idx];
				rr.add(new int[] { idx, next });
				n--;
				continue;
			}
			if (n == 0) {
				continue;
			}
			if (!ll.isEmpty()) {
				t = ll.peek()[1];
				if (!rr.isEmpty()) {
					t = Math.min(rr.peek()[1], t);
				}
			} else {
				t = rr.peek()[1];
			}
		}
		int ans = 0;
		while (!rr.isEmpty() || !right.isEmpty()) {
			while (!ll.isEmpty() && ll.peek()[1] <= t) {
				int[] cur = ll.poll();
				left.add(new int[] { cur[0], sum[cur[0]] });
			}
			while (!rr.isEmpty() && rr.peek()[1] <= t) {
				int[] cur = rr.poll();
				right.add(new int[] { cur[0], sum[cur[0]] });
			}
			if (!right.isEmpty()) {
				int[] cur = right.poll();
				int idx = cur[0], s = cur[1];
				t += r[idx];
				if (rr.isEmpty() && right.isEmpty()) {
					ans = t;
				}
				int next = t + w[idx];
				ll.add(new int[] { idx, next });
				continue;
			} 
			
			if (!ll.isEmpty()) {
				t = ll.peek()[1];
				if (!rr.isEmpty()) {
					t = Math.min(rr.peek()[1], t);
				}
			} else {
				t = rr.peek()[1];
			}
		}
		return ans;
	}
}
